

// LCR 097.不同的子序列
class Solution {
    typedef unsigned long long LL;
public:
    int numDistinct(string s, string t) {
        // 使用一个二维DP表来实现
        int n1 = s.size() , n2 = t.size();

        vector<vector<LL>> dp(n2 + 1, vector<LL>(n1 + 1));   // dp[i][j]表示 , t以i位置结尾 , s以j位置结尾时 ,s中包含t[0,i]的子序列的个数
        for(int i = 0 ; i <= n1 ; i++)
            dp[0][i] = 1;
        
        for(int i = 1 ; i <= n2 ; i++ )
        {
            for(int j = 1 ; j <= n1 ; j++)
            {
                if(s[j - 1] == t[i - 1]) dp[i][j] = dp[i - 1][j - 1] + dp[i][j - 1];
                else dp[i][j] = dp[i][j - 1];
            }
        }
        return dp[n2][n1];
    }
};